home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / devel / tcl / tclx7_31.z / tclx7_31 / tcldev / tclX7.3a-p1 / src / tclXregexp.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-11-19  |  16.9 KB  |  518 lines
  1. /*
  2.  * tclXregexp.c --
  3.  *
  4.  * Tcl regular expression pattern matching utilities.
  5.  *-----------------------------------------------------------------------------
  6.  * Copyright 1991-1993 Karl Lehenbauer and Mark Diekhans.
  7.  *
  8.  * Permission to use, copy, modify, and distribute this software and its
  9.  * documentation for any purpose and without fee is hereby granted, provided
  10.  * that the above copyright notice appear in all copies.  Karl Lehenbauer and
  11.  * Mark Diekhans make no representations about the suitability of this
  12.  * software for any purpose.  It is provided "as is" without express or
  13.  * implied warranty.
  14.  *-----------------------------------------------------------------------------
  15.  * Boyer-Moore code from: 
  16.  *     torek-boyer-moore/27-Aug-90 by
  17.  *     chris@mimsy.umd.edu (Chris Torek)
  18.  *-----------------------------------------------------------------------------
  19.  * $Id: tclXregexp.c,v 3.0 1993/11/19 06:59:11 markd Rel $
  20.  *-----------------------------------------------------------------------------
  21.  */
  22.  
  23. #include "tclExtdInt.h"
  24.  
  25. /*
  26.  * This is declared in tclUtil.c.  Must be set to NULL before compiling
  27.  * a regular expressions.
  28.  */
  29. extern char *tclRegexpError;
  30.  
  31. /*
  32.  * Meta-characters for regular expression
  33.  */
  34. #define REXP_META                   "^$.[()|?+*\\"
  35. #define REXP_META_NO_BRACKET_NO_OR  "^$.()?+*\\"
  36.  
  37. #ifndef CHAR_MAX
  38. #    define CHAR_MAX 255
  39. #endif
  40.  
  41. /*
  42.  * Prototypes of internal functions.
  43.  */
  44.  
  45. static char *
  46. BoyerMooreCompile _ANSI_ARGS_((char *pat,
  47.                                   int patlen));
  48.  
  49. static char *
  50. BoyerMooreExecute _ANSI_ARGS_((char     *text,
  51.                                unsigned  textlen,
  52.                                char     *compPtr,
  53.                                unsigned *patLenP));
  54.  
  55. static int
  56. FindNonRegExpSubStr _ANSI_ARGS_((char  *expression,
  57.                                  char **subStrPtrPtr));
  58.  
  59.  
  60. /*
  61.  * Boyer-Moore search: input is `text' (a string) and its length,
  62.  * and a `pattern' (another string) and its length.
  63.  *
  64.  * The linear setup cost of this function is approximately 256 + patlen.
  65.  * Afterwards, however, the average cost is O(textlen/patlen), and the
  66.  * worst case is O(textlen+patlen).
  67.  *
  68.  * The Boyer-Moore algorithm works by observing that, for each position
  69.  * in the text, if the character there does *not* occur somewhere in the
  70.  * search pattern, no comparisons including that character will match.
  71.  * That is, given the text "hello world..." and the pattern "goodbye", the
  72.  * `w' in `world' means that none of `hello w', `ello wo', `llo wor',
  73.  * `lo worl', `o world', ` world.', and `world..' can match.  In fact,
  74.  * exactly patlen strings are certain not to match.  We can discover this
  75.  * simply by looking at the patlen'th character.  Furthermore, even if
  76.  * the text character does occur, it may be that it rules out some number
  77.  * of other matches.  Again, we can discover this by doing the match
  78.  * `backwards'.
  79.  *
  80.  * We set up a table of deltas for each possible character, with
  81.  * delta[character] being patlen for characters not in the pattern,
  82.  * less for characters in the pattern, growing progressively smaller
  83.  * as we near the end of the pattern.  Matching then works as follows:
  84.  *
  85.  *       0         1         2         3
  86.  *       01234567890123456789012345678901234567
  87.  *      "Here is the string being searched into"        (text)
  88.  *       ------                                         (pos = [0..5])
  89.  *      "string"                                        (pat)
  90.  *      654321-                                         (deltas)
  91.  *
  92.  * (the delta for `-' will be derived below).
  93.  *
  94.  * Positions 0..5 end with `i', which is not the `g' we want.  `i' does
  95.  * appear in `string', but two characters before the end.  We skip
  96.  * forward so as to make the `i's match up:
  97.  *
  98.  *      "Here is the string being searched into"        (text)
  99.  *        "string"                                      (pos = [2..7])
  100.  *
  101.  * Next we find that ` ' and `g' do not match.  Since ` ' does not appear
  102.  * in the pattern at all, we can skip forward 6:
  103.  *
  104.  *      "Here is the string being searched into"        (text)
  105.  *              "string"                                (pos = [8..13])
  106.  *
  107.  * Comparing `t' vs `g', we again find no match, and so we obtain the
  108.  * delta for `t', which is 4.  We skip to position 17:
  109.  *
  110.  *      "Here is the string being searched into"        (text)
  111.  *                  "string"                            (pos = [12..17])
  112.  *
  113.  * It thus takes only four steps to move the search point forward to the
  114.  * match, in this case.
  115.  *
  116.  * If the pattern has a recurring character, we must set the delta for
  117.  * that character to the distance of the one closest to the end:
  118.  *
  119.  *      "befuddle the cat"      (text)
  120.  *      "fuddle"                (pos = [0..5])
  121.  *      654321-                 (delta)
  122.  *
  123.  * We want the next search to line the `d's up like this:
  124.  *
  125.  *      "befuddle the cat"      (text)
  126.  *        "fuddle"              (pos = [2..7])
  127.  *
  128.  * and not like this:
  129.  *
  130.  *      "befuddle the cat"      (text)
  131.  *         "fuddle"             (pos = [3..8])
  132.  *
  133.  * so we take the smaller delta for d, i.e., 2.
  134.  *
  135.  * The last task is computing the delta we have noted above as `-':
  136.  *
  137.  *      "candlesticks"          (text)
  138.  *      "hand"                  (pos = [0..3])
  139.  *      4321-                   (delta)
  140.  *
  141.  * Here the `d' in `hand' matches the `d' in `candlesticks', but the
  142.  * strings differ.  Since there are no other `d's in `hand', we know
  143.  * that none of (cand,andl,ndle,dles) can match, and thus we want this
  144.  * delta to be 4 (the length of the pattern).  But if we had, e.g.:
  145.  *
  146.  *      "candlesticks"          (text)
  147.  *      "deed"                  (pos = [0..3])
  148.  *      4321-                   (delta)
  149.  *
  150.  * then we should advance to line up the other `d':
  151.  *
  152.  *      "candlesticks"          (text)
  153.  *         "deed"               (pos = [3..6])
  154.  *
  155.  * As this suggests, the delta should be that for the `d' nearest the
  156.  * end, but not including the end.  This is easily managed by setting up
  157.  * a delta table as follows:
  158.  *
  159.  *      for int:c in [0..255] { delta[c] = patlen; };
  160.  *      for int:x in [0..patlen-1) { delta[pat[x]] = patlen - (x + 1); };
  161.  *
  162.  * delta[pat[patlen-1]] is never written, so the last letter inherits the
  163.  * delta from an earlier iteration or from the previous loop.
  164.  *
  165.  * NB: the nonsense with `deltaspace' below exists merely because gcc
  166.  * does a horrible job of common subexpression elimination (it does not
  167.  * notice that the array is at a constant stack address).
  168.  */
  169.  
  170. struct compiled_search_struct {
  171.         unsigned patlen;
  172.         unsigned deltaspace[CHAR_MAX + 1];
  173. };
  174.  
  175.  
  176. static char *
  177. BoyerMooreCompile (pat, patlen)
  178.     char *pat;
  179.     int   patlen;
  180. {
  181.         register unsigned char *p, *t;
  182.         register unsigned i, p1, j, *delta;
  183.         struct compiled_search_struct *cp;
  184.         int alloc_len;
  185.  
  186.         /*
  187.          * Algorithm fails if pattern is empty.
  188.          */
  189.         if ((p1 = patlen) == 0)
  190.                 return (NULL);
  191.  
  192.         alloc_len = sizeof(struct compiled_search_struct) + patlen + 1;
  193.         cp = (struct compiled_search_struct *) ckalloc (alloc_len);
  194.  
  195.         strncpy((char *)cp+sizeof(struct compiled_search_struct), pat, patlen);
  196.         *((char *)cp+alloc_len-1) = '\0';
  197.  
  198.         /* set up deltas */
  199.         delta = cp->deltaspace;
  200.  
  201.         for (i = 0; i <= CHAR_MAX; i++)
  202.                 delta[i] = p1;
  203.  
  204.         for (p = (unsigned char *)pat, i = p1; --i > 0;)
  205.                 delta[*p++] = i;
  206.  
  207.         cp->patlen = patlen;
  208.         return((char*) cp);
  209. }
  210.  
  211. static char *
  212. BoyerMooreExecute (text, textlen, compPtr, patLenP)
  213.         char     *text;
  214.         unsigned  textlen;
  215.         char     *compPtr;
  216.         unsigned *patLenP;
  217. {
  218.         register unsigned char *p, *t;
  219.         struct compiled_search_struct *csp = 
  220.             (struct compiled_search_struct*) compPtr;
  221.         register unsigned i, j, *delta = csp->deltaspace;
  222.         int p1;
  223.         char *pat;
  224.         unsigned patlen;
  225.  
  226.         *patLenP = p1 = patlen = csp->patlen;
  227.         /* code below fails (whenever i is unsigned) if pattern too long */
  228.         if (p1 > textlen)
  229.                 return (NULL);
  230.  
  231.         pat = (char *)csp + sizeof(struct compiled_search_struct);
  232.         /*
  233.          * From now on, we want patlen - 1.
  234.          * In the loop below, p points to the end of the pattern,
  235.          * t points to the end of the text to be tested against the
  236.          * pattern, and i counts the amount of text remaining, not
  237.          * including the part to be tested.
  238.          */
  239.         p1--;
  240.         p = (unsigned char *)pat + p1;
  241.         t = (unsigned char *)text + p1;
  242.         i = textlen - patlen;
  243.         for (;;) {
  244.                 if (*p == *t && 
  245.                     memcmp((p - p1), (t - p1), p1) == 0)
  246.                         return ((char *)t - p1);
  247.                 j = delta[*t];
  248.                 if (i < j)
  249.                         break;
  250.                 i -= j;
  251.                 t += j;
  252.         }
  253.         return (NULL);
  254. }
  255.  
  256.  
  257. /*
  258.  *-----------------------------------------------------------------------------
  259.  *
  260.  * Tcl_RegExpClean --
  261.  *     Free all resources associated with a regular expression info 
  262.  *     structure..
  263.  *
  264.  *-----------------------------------------------------------------------------
  265.  */
  266. void
  267. Tcl_RegExpClean (regExpPtr)
  268.     Tcl_regexp *regExpPtr;
  269. {
  270.     if (regExpPtr->progPtr != NULL)
  271.         ckfree ((char *) regExpPtr->progPtr);
  272.     if (regExpPtr->boyerMoorePtr != NULL)
  273.         ckfree ((char *) regExpPtr->boyerMoorePtr);
  274. }
  275.  
  276. /*
  277.  *-----------------------------------------------------------------------------
  278.  *
  279.  * FindNonRegExpSubStr
  280.  *     Find the largest substring that does not have any regular 
  281.  *     expression meta-characters and is not located within `[...]'.
  282.  *     If the regexp contains an or (|), zero is returned, as the 
  283.  *     Boyer-Moore optimization does not work, since there are actually
  284.  *     multiple patterns.  The real solution is to build the Boyer-Moore
  285.  *     into the regular expression code.
  286.  *-----------------------------------------------------------------------------
  287.  */
  288. static int
  289. FindNonRegExpSubStr (expression, subStrPtrPtr)
  290.     char  *expression;
  291.     char **subStrPtrPtr;
  292. {
  293.     register char *subStrPtr = NULL;
  294.     register char  subStrLen = 0;
  295.     register char *scanPtr   = expression;
  296.     register int   len;
  297.  
  298.     while (*scanPtr != '\0') {
  299.         len = strcspn (scanPtr, REXP_META);
  300.         /*
  301.          * If we are at a meta-character, by-pass till non-meta.  If we hit
  302.          * a `[' then by-pass the entire `[...]' range, but be careful, could
  303.          * have omitted `]'.  In a `|' is encountered (except in brackets),'
  304.          * we are through.
  305.          */
  306.         if (len == 0) {
  307.             scanPtr += strspn (scanPtr, REXP_META_NO_BRACKET_NO_OR);
  308.             if (*scanPtr == '|')
  309.                 return 0;
  310.             if (*scanPtr == '[') {
  311.                 scanPtr += strcspn (scanPtr, "]");
  312.                 if (*scanPtr == ']')
  313.                     scanPtr++;
  314.             }          
  315.         } else {
  316.             if (len > subStrLen) {
  317.                 subStrPtr = scanPtr;
  318.                 subStrLen = len;
  319.             }
  320.             scanPtr += len;
  321.         }
  322.     }
  323.     *subStrPtrPtr = subStrPtr;
  324.     return subStrLen;
  325. }
  326.  
  327. /*
  328.  *-----------------------------------------------------------------------------
  329.  *
  330.  * Tcl_RegExpCompile --
  331.  *     Compile a regular expression.
  332.  *
  333.  * Parameters:
  334.  *     o regExpPtr - Used to hold info on this regular expression.  If the
  335.  *       structure is being reused, it Tcl_RegExpClean should be called first.
  336.  *     o expression - Regular expression to compile.
  337.  *     o flags - The following flags are recognized:
  338.  *         o REXP_NO_CASE - Comparison will be regardless of case.
  339.  *         o REXP_BOTH_ALGORITHMS - If specified, a Boyer-Moore expression is 
  340.  *           compiled for the largest substring of the expression that does
  341.  *           not contain any meta-characters.  This is slows compiling, but
  342.  *           speeds up large searches.
  343.  *
  344.  * Results:
  345.  *     Standard TCL results.
  346.  *-----------------------------------------------------------------------------
  347.  */
  348. int
  349. Tcl_RegExpCompile (interp, regExpPtr, expression, flags)
  350.     Tcl_Interp  *interp;
  351.     Tcl_regexp  *regExpPtr;
  352.     char        *expression;
  353.     int          flags;
  354. {
  355.     char *expBuf;
  356.     int   anyMeta;
  357.  
  358.     if (*expression == '\0') {
  359.         Tcl_AppendResult (interp, "Null regular expression", (char *) NULL);
  360.         return TCL_ERROR;
  361.     }
  362.  
  363.     regExpPtr->progPtr = NULL;
  364.     regExpPtr->boyerMoorePtr = NULL;
  365.     regExpPtr->noCase = flags & REXP_NO_CASE;
  366.  
  367.     if (flags & REXP_NO_CASE) {
  368.         expBuf = ckalloc (strlen (expression) + 1);
  369.         Tcl_DownShift (expBuf, expression);
  370.     } else
  371.         expBuf = expression;
  372.  
  373.     anyMeta = strpbrk (expBuf, REXP_META) != NULL;
  374.  
  375.     /*
  376.      * If no meta-characters, use Boyer-Moore string matching only.
  377.      */
  378.     if ((!anyMeta) && (flags & REXP_BOTH_ALGORITHMS)) {
  379.         regExpPtr->boyerMoorePtr = BoyerMooreCompile (expBuf, strlen (expBuf));
  380.         goto okExitPoint;
  381.     }
  382.  
  383.     /*
  384.      * Build a Boyer-Moore on the largest non-meta substring, if requested,
  385.      * and the reg-exp does not contain a `|' (or).  If less that three
  386.      * characters in the string, don't use B-M, as it seems not optimal at
  387.      * this point.
  388.      */
  389.     if (flags & REXP_BOTH_ALGORITHMS) {
  390.         char *subStrPtr;
  391.         int   subStrLen;
  392.         
  393.         subStrLen = FindNonRegExpSubStr (expBuf, &subStrPtr);
  394.         if (subStrLen > 2)
  395.             regExpPtr->boyerMoorePtr = 
  396.                 BoyerMooreCompile (subStrPtr, subStrLen);
  397.     }
  398.     
  399.     /*
  400.      * Compile meta-character containing regular expression.
  401.      */
  402.     tclRegexpError = NULL;
  403.     regExpPtr->progPtr = TclRegComp (expBuf);
  404.     if (tclRegexpError != NULL) {
  405.         if (flags & REXP_NO_CASE)
  406.             ckfree (expBuf);
  407.         Tcl_AppendResult (interp, "error in regular expression: ", 
  408.                           tclRegexpError, (char *) NULL);
  409.         if (flags & REXP_NO_CASE)
  410.             ckfree (expBuf);
  411.         Tcl_RegExpClean (regExpPtr);
  412.     }
  413.   
  414. okExitPoint: 
  415.     if (flags & REXP_NO_CASE)
  416.         ckfree (expBuf);
  417.     return TCL_OK;
  418.  
  419. }
  420.  
  421. /*
  422.  *-----------------------------------------------------------------------------
  423.  *
  424.  * Tcl_RegExpExecute --
  425.  *     Execute a regular expression compiled with Boyer-Moore and/or 
  426.  *     regexp.
  427.  *
  428.  * Parameters:
  429.  *     o regExpPtr - Used to hold info on this regular expression.
  430.  *     o matchStrIn - String to match against the regular expression.
  431.  *     o matchStrLower - Optional lower case version of the string.  If
  432.  *       multiple no case matches are being done, time can be saved by
  433.  *       down shifting the string in advance.  NULL if not a no-case 
  434.  *       match or this procedure is to do the down shifting.
  435.  *     o subMatchInfo - A array of entries containing the indexs and
  436.  *       lengths of each submatch.  Teminated by an entry of -1, -1.
  437.  * Results:
  438.  *     TRUE if a match, FALSE if it does not match.
  439.  *
  440.  *-----------------------------------------------------------------------------
  441.  */
  442. int
  443. Tcl_RegExpExecute (interp, regExpPtr, matchStrIn, matchStrLower, subMatchInfo)
  444.     Tcl_Interp       *interp;
  445.     Tcl_regexp       *regExpPtr;
  446.     char             *matchStrIn;
  447.     char             *matchStrLower;
  448.     Tcl_SubMatchInfo  subMatchInfo;
  449. {
  450.     char   *matchStr;
  451.     int     result, idx;
  452.     regexp *progPtr;
  453.  
  454.     if (regExpPtr->noCase) {
  455.         if (matchStrLower == NULL) {
  456.             matchStr = ckalloc (strlen (matchStrIn) + 1);
  457.             Tcl_DownShift (matchStr, matchStrIn);
  458.         } else
  459.             matchStr = matchStrLower;
  460.     } else {
  461.         matchStr = matchStrIn;
  462.     }
  463.  
  464.     /*
  465.      * If a Boyer-Moore pattern has been compiled, use that algorithm to test
  466.      * against the text.  If that passes, then test with the regexp if we have
  467.      * it.
  468.      */
  469.     if (regExpPtr->boyerMoorePtr != NULL) {
  470.         char     *startPtr;
  471.         unsigned  matchLen;
  472.  
  473.         startPtr = BoyerMooreExecute (matchStr, strlen (matchStr), 
  474.                                       regExpPtr->boyerMoorePtr, &matchLen);
  475.         if (startPtr == NULL) {
  476.             result = FALSE;
  477.             goto exitPoint;
  478.         }
  479.         /* 
  480.          * If no regexp, its a match!
  481.          */
  482.         if (regExpPtr->progPtr == NULL) {
  483.             subMatchInfo [0].start = -1;
  484.             subMatchInfo [0].end = -1;
  485.             result = TRUE; 
  486.             goto exitPoint;
  487.         }
  488.     }
  489.     
  490.     /*
  491.      * Give it a go with full regular expressions
  492.      */
  493.     progPtr = regExpPtr->progPtr;
  494.     result = TclRegExec (progPtr, matchStr, matchStr);
  495.  
  496.     /*
  497.      * Return submatches if we found it.
  498.      */
  499.     if (result) {
  500.         for (idx = 1; idx < NSUBEXP; idx++) {
  501.             if (progPtr->startp [idx] == NULL)
  502.                 break;
  503.             subMatchInfo [idx - 1].start = progPtr->startp [idx] - matchStr;
  504.             subMatchInfo [idx - 1].end = progPtr->endp [idx] - matchStr - 1;
  505.         }
  506.         subMatchInfo [idx - 1].start = -1;
  507.         subMatchInfo [idx - 1].end = -1;
  508.     }
  509.  
  510.     /*
  511.      * Clean up and return status here.
  512.      */
  513. exitPoint:
  514.     if ((regExpPtr->noCase) && (matchStrLower == NULL))
  515.         ckfree (matchStr);
  516.     return result;
  517. }
  518.